package com.study.algorithm.base.list;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * XorCalculate
 *
 * @author wanghuilong
 * @version 1.0
 * @description xor calculate
 * @date 2022/11/6 15:17
 */
public class XorCalculate {

    /*
    一个数组：int arr[N]
    1、一种数出现了奇数次，其他数字都出现了偶数次，求这一种出现了奇数次的数字
    2、两种数出现了奇数次，其他数字都出现了偶数次，求这两种出现了奇数次的数字
    要求：时间复杂度 O(N) , 额外空间复杂度 O(1)
     */

    public static final List<Integer> list1 = Lists.newArrayList(1,2,3,4,1,2,3);

    public static final List<Integer> list2 = Lists.newArrayList(1,2,3,4,1,2,3,5);


    public static void main(String[] args) {
        calculateMethod1(list1);
        calculateMethod2(list2);
        System.out.println(~1);
    }

    public static void calculateMethod1(List<Integer> list) {
        int eor = 0;
        for (int i = 0; i < list.size(); i++) {
            eor = eor ^ list.get(i);
        }
        System.out.println(eor);
    }


    public static void calculateMethod2(List<Integer> list) {
        int eor = 0;
        for (int i = 0; i < list.size(); i++) {
            eor = eor ^ list.get(i);
        }
        //eor必然不为0， 取出eor二进制位上最右边的1
        //取出最右边的1 ： 一个数取反(~) 加一 ，&上本身的值
        int rightOne = eor & (~eor + 1);
        int onlyOne = 0;
        for (int i = 0; i < list.size(); i++)   {
            if((list.get(i) & rightOne) == 0) {
                onlyOne = onlyOne ^ list.get(i);
            }
        }

        System.out.println(onlyOne+","+(onlyOne ^ eor));
    }

}
